package com.timous.动态规划;

/**
 * @author Timous
 * @create 2020-12-21 16:40
 **/
public class _746_使用最小花费爬楼梯 {

    public static void main(String[] args) {
        int[] cost = new int[]{0,1,1,0};

        System.out.println(minCostClimbingStairs(cost));
    }

    public static int minCostClimbingStairs2(int[] cost) {
        int[] dp = new int[cost.length]; // dp[i] 为爬到第i级台阶的最低耗费体力值
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < dp.length; i++) {
            dp[i] = min(dp[i-1] , dp[i-2]) + cost[i];
        }
        return min(dp[cost.length - 1] , dp[cost.length - 2]);
    }
    public static int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[3]; // dp[i] 为爬到第i级台阶的最低耗费体力值
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < cost.length; i++) {
            dp[2] = min(dp[0] , dp[1]) + cost[i];
            dp[0] = dp[1];
            dp[1] = dp[2];
        }
        return min(dp[0] , dp[1]);
    }
    public static int min(int a, int b){
        return a > b ? b : a;
    }
}
